/*
 * @lc app=leetcode.cn id=381 lang=cpp
 *
 * [381] O(1) 时间插入、删除和获取随机元素 - 允许重复
 */

// @lc code=start
#include <bits/stdc++.h>
using namespace std;
class RandomizedCollection
{
    unordered_map<int, unordered_set<int>> m;
    vector<int> v;

public:
    RandomizedCollection()
    {
    }

    bool insert(int val)
    {
        bool ret = true;
        auto it = m.find(val);
        if (it != m.end())
        {
            ret = false;
        }

        v.push_back(val);
        m[val].insert(v.size() - 1);

        return ret;
    }

    bool remove(int val)
    {
        auto it = m.find(val);
        if (it == m.end())
            return false;

        if (val == v[v.size() - 1])
        {
            m[val].erase(v.size() - 1);
            if (m[val].empty())
                m.erase(it);
            v.pop_back();
            return true;
        }

        const int inx_val = *(it->second.begin());
        if (inx_val != v.size() - 1)
        {
            const int inx_new_val = v.size() - 1;
            const int new_val = v[inx_new_val];

            swap(v[inx_val], v[inx_new_val]);

            m[new_val].erase(inx_new_val);
            m[new_val].insert(inx_val);
        }

        m[val].erase(inx_val);
        if (m[val].empty())
        {
            m.erase(it);
        }

        v.pop_back();

        return true;
    }

    int getRandom()
    {
        const int n = random() % v.size();
        return v[n];
    }
};

/**
 * Your RandomizedCollection object will be instantiated and called as such:
 * RandomizedCollection* obj = new RandomizedCollection();
 * bool param_1 = obj->insert(val);
 * bool param_2 = obj->remove(val);
 * int param_3 = obj->getRandom();
 */
// @lc code=end
// int main(int argc, char const *argv[])
// {

//     RandomizedCollection c;
//     c.insert(1);
//     c.insert(1);
//     c.insert(2);
//     c.insert(1);
//     c.insert(2);
//     c.insert(2);

//     c.remove(1);
//     c.remove(2);
//     c.remove(2);
//     c.remove(2);

//     cout << c.getRandom() << endl;
//     cout << c.getRandom() << endl;
//     cout << c.getRandom() << endl;
//     cout << c.getRandom() << endl;
//     cout << c.getRandom() << endl;
//     cout << c.getRandom() << endl;
//     cout << c.getRandom() << endl;

//     return 0;
// }
